/*
 * @lc app=leetcode.cn id=1723 lang=typescript
 *
 * [1723] 完成所有工作的最短时间
 */

// @lc code=start
function minimumTimeRequired(jobs: number[], k: number): number {
  let ans = Number.POSITIVE_INFINITY;
  const slot = new Array(k).fill(0);
  const backtrack = (jobs: number[], idx: number, slot: number[], maxNum: number) => {
    if (idx === jobs.length) {
      // 如果已经遍历完所有的工作，则更新答案
      ans = maxNum;
      return;
    }
    const k = slot.length;
    // 给工人分配下标为idx的任务
    for (let i = 0; i < k; i++) {
      // 当前工人的工作总时长大于结果，当前工人不需要分配工作，换下一个工人
      if (slot[i] + jobs[idx] > ans) continue;
      slot[i] += jobs[idx];
      backtrack(jobs, idx + 1, slot, Math.max(maxNum, slot[i]));
      slot[i] -= jobs[idx];
      // 当前工人只有一个工作，已经处理过了，可以不用再分配了
      if (slot[i] === 0) break;
    }
  };
  backtrack(jobs, 0, slot, 0);
  return ans;
}
// @lc code=end
